package com.xyhuo.leetcode.december;

import com.xyhuo.leetcode.common.TreeNode;

import java.util.*;

/**
 * 从二叉搜索树到更大和树
 * https://leetcode.cn/problems/binary-search-tree-to-greater-sum-tree/
 *
 * @time 2023/12/4
 */
public class BstToGst {

//    public static void main(String[] args) {
//        TreeNode t0 = new TreeNode(0);
//        TreeNode t1 = new TreeNode(1);
//        TreeNode t2 = new TreeNode(2);
//        TreeNode t3 = new TreeNode(3);
//        TreeNode t4 = new TreeNode(4);
//        TreeNode t5 = new TreeNode(5);
//        TreeNode t6 = new TreeNode(6);
//        TreeNode t7 = new TreeNode(7);
//        TreeNode t8 = new TreeNode(8);
//
//        t1.left = t0;
//        t1.right = t2;
//        t2.right = t3;
//        t4.left = t1;
//        t4.right = t6;
//        t6.left = t5;
//        t6.right = t7;
//        t7.right = t8;
//
//        BstToGst bst = new BstToGst();
//        bst.bstToGst(t4);
//    }

    public TreeNode bstToGst(TreeNode root) {
        Deque<Integer> deque = new ArrayDeque<>();
        int all = childValue(root, deque);
        calculate(root, deque, all);
        return root;
    }

    private void calculate(TreeNode root, Deque<Integer> deque, int all) {
        if (null == root) {
            return;
        }
        calculate(root.left, deque, all);
        if (!deque.isEmpty()) {
            Integer first = deque.removeFirst();
            root.val += all - first;
        }
        calculate(root.right, deque, all);
    }

    private int childValue(TreeNode root, Deque<Integer> deque) {
        if (null == root) {
            return 0;
        }
        int leftVal = childValue(root.left, deque);
        if (deque.isEmpty()) {
            deque.addLast(root.val);
        } else {
            int lastVal = deque.getLast();
            deque.addLast(lastVal + root.val);
        }
        int rightVal = childValue(root.right, deque);

        return root.val + leftVal + rightVal;
    }
}
